This paper looks at the problem of representing simple routes on a graph as a probability distribution using Probabilistic Sentential Decision Diagrams (PSDDs). Representing a complex structure such as a graph is difficult, and the authors transform the problem by turning a graph into a Boolean circuit where it is straightforward to perform inference, and as an experiment, use their method on a route prediction method for San Francisco taxi cabs, where it beats two baselines. PSDDs refer to a framework that represents probability distributions over structured objects through Boolean circuits. Once the object is depicted as a Boolean circuit, it becomes straightforward to parameterize it. More formally, PSDD's are parameterized by including a distribution over each or-gate, and PSDD's can represent any distribution (and under some conditions, this distribution is unique).

Recently, the Probabilistic Sentential Decision Diagram (PSDD) has been proposed as a framework for systematically inducing and learning distributions over structured objects, including combinatorial objects such as permutations and rankings, paths and matchings on a graph, etc. In this paper, we study the scalability of such models in the context of representing and learning distributions over routes on a map. In particular, we introduce the notion of a hierarchical route distribution and show how they can be leveraged to construct tractable PSDDs over route distributions, allowing them to scale to larger maps. We illustrate the utility of our model empirically, in a route prediction task, showing how accuracy can be increased significantly compared to Markov models. Papers published at the Neural Information Processing Systems Conference.